package vip.zhenzicheng.algorithm.leetcode.binary_tree;

import vip.zhenzicheng.algorithm.TreeNode;

/**
 * <a href="https://leetcode.cn/problems/diameter-of-binary-tree/">二叉树的直径 [简单]</a>
 *
 * @author zhenzicheng
 * @date 2022-07-06 18:24
 */
public class DiameterOfBinaryTree_543 {

  int max = 0;

  public static void main(String[] args) {
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);
    TreeNode ll = root.left;
    ll.left = new TreeNode(4);
    ll.right = new TreeNode(5);

    DiameterOfBinaryTree_543 test = new DiameterOfBinaryTree_543();
    int i = test.diameterOfBinaryTree(root);
    System.out.println(i);
  }

  public int diameterOfBinaryTree(TreeNode root) {
    maxDepth(root);
    return max;
  }

  public int maxDepth(TreeNode root) {
    if (root == null) {
      return 0;
    }
    int left = maxDepth(root.left); // 递归找左子树
    int right = maxDepth(root.right); // 递归找右子树

    max = Math.max(max, left + right); // 每次在递归中都计算当前左右距离最长的距离

    return Math.max(left, right) + 1; // 返回的只是左右字数层数较大（路径最长）的
  }
}
